package com.example.binarytree;

import com.example.structure.TreeNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 输出所有二叉树路径和
 */
public class AllBinaryTreePath {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> res = new ArrayList<>();
        Deque<Integer> paths = new LinkedList<>();
        constructPaths(root, paths, res);
        return res;
    }

    public void constructPaths(TreeNode root, Deque<Integer> paths, List<List<Integer>> res) {
        if (root != null) {
            paths.add(root.val);//根
            if (root.left == null && root.right == null) {  // 当前节点是叶子节点
                res.add(new ArrayList<>(paths));
                // 把路径加入到答案中
            } else {
                constructPaths(root.left, paths, res);//左
                constructPaths(root.right, paths, res);//右
            }
            paths.pollLast();
        }
    }
}
